

def sumArray(alist):
    """
    >>> alist = range(128)
    >>> b = TreeArray(alist)
    >>> b.sumArray() == sumArray(alist)
    True
    >>> alist[3] = 100
    >>> b.set(3, 100)
    >>> b.sumArray() == sumArray(alist)
    True
    """
    clist = alist[:]
    for i, v in enumerate(clist[1:], 1):
        clist[i] += clist[i-1]
    return clist

class TreeArray():
    @classmethod
    def createTreeArray(self, alist):
        clist = alist[:]
        l = len(alist)
        cur, prev = 2, 1
        while cur <= l:
            for i in xrange(cur-1, l, cur):
                clist[i] = clist[i] + clist[i-prev]
            cur, prev = cur*2, cur
        return clist 
    def __init__(self, alist):
        self.clist = TreeArray.createTreeArray(alist)
        #self.alist = list(alist)[:]
        self.alist = [i for i in alist]
    def getSum(self, idx):
        idx += 1
        #l = idx & (idx ^ (idx-1))
        l = (idx & -idx)
        diff = idx
        s = 0
        while diff != 0:
            if (diff & l) != 0:
                s += self.clist[diff-1]
                diff -= l
            l <<= 1
        return s
    def sumArray(self):
        return [self.getSum(i) for i in xrange(len(self.clist))]
    def get(self, i):
        return self.alist[i]
    def set(self, i, num):
        diff = num - self.alist[i]
        self.alist[i] = num
        self.clist[i] += diff
        t = 1;
        while (t<=i+1): t<<=1
        while t<=len(self.clist):
            self.clist[t-1] += diff
            t <<= 1
    
        
if __name__ == "__main__":
    import doctest
    doctest.testmod()
    
